#include <iostream>
#include <sstream>

#include <cassert>
#include <memory>
#include <queue>
#include <string>
#include <vector>

#ifndef ASSERT
#define ASSERT(x) assert(x)
#endif

struct Txpr {
    std::string name;
    std::vector<struct Txpr*> factors;

    Txpr() = default;

    ~Txpr() {
        for (size_t i = 0; i < factors.size(); i++) {
            delete factors[i];
        }
    }

    // 判断两个类型是否相等
    static inline bool eq(const Txpr& a, const Txpr& b) {
        if ((a.name != b.name) || (a.factors.size() != b.factors.size())) {
            return false;
        }

        for (size_t i = 0; i < a.factors.size(); i++) {
            if (!Txpr::eq(*a.factors[i], *b.factors[i])) {
                return false;
            }
        }

        return true;
    }

    // 克隆一个自身
    Txpr* clone() const {
        Txpr* type = new Txpr;
        type->name = name;
        for (size_t i = 0; i < factors.size(); i++) {
            type->factors.push_back(factors[i]->clone());
        }

        return type;
    }

    // 打印完整格式
    std::string string() const {
        std::stringstream result;
        result << name;
        if (factors.size() > 0) {
            result << "<";
            for (size_t i = 0; i < factors.size(); i++) {
                result << ((i > 0) ? "," : "") << factors[i]->string();
            }
            result << ">";
        }
        return result.str();
    }

    Txpr& with(Txpr* factor) {
        factors.push_back(factor);
        return *this;
    }

    // 拆词法
    static std::string next(const std::string& name, size_t& pos) {

        while (name[pos] == ' ') {
            pos++;
        }

        switch (name[pos]) {
            case '<':
            case '>':
            case ',':
                return std::string(1, name[pos++]);
            default: {
                int start = pos;
                while (std::isalnum(name[++pos])) {
                }
                return name.substr(start, pos - start);
            }
        }
    }

    Txpr& expect(const std::string& name, size_t& pos, const std::string& s) {
        auto token = next(name, pos);
        ASSERT(token == s);
        return *this;
    }

    Txpr& expect(const std::string& name, size_t& pos) {
        auto factor = load(name, pos);
        ASSERT(factor != nullptr);
        factors.push_back(factor);
        return *this;
    }

    static inline Txpr& make(const std::string& name) {
        auto type = new Txpr;
        type->name = name;
        return *type;
    }

    // 处理语法
    static struct Txpr* load(const std::string& name, size_t& pos) {
        auto token = std::move(next(name, pos));
        if (token == "list") {
            return &make("list")//
                        .expect(name, pos, "<")
                        .expect(name, pos)
                        .expect(name, pos, ">");
        }

        if (token == "map") {
            return &make("map")//
                        .expect(name, pos, "<")
                        .expect(name, pos)
                        .expect(name, pos, ",")
                        .expect(name, pos)
                        .expect(name, pos, ">");
        }

        if (std::isalnum(token[0])) {
            return &make(token);
        }

        return nullptr;
    }
};

// 规则1：
// complex -> real
// real -> int
Txpr* try_rule1(const Txpr& type) {
    if (type.name == "complex") {
        return &Txpr::make("real");
    }

    if (type.name == "real") {
        return &Txpr::make("int");
    }

    return nullptr;
}

// 规则2：
// list<T>->T
Txpr* try_rule2(const Txpr& type) {
    if (type.name == "list") {
        return type.factors[0]->clone();
    }

    return nullptr;
}

// 规则3：
// list<complex>->list<real>
// list<real>->list<int>
Txpr* try_rule3(const Txpr& type) {
    if (type.name == "list") {
        if (type.factors[0]->name == "complex") {
            return &Txpr::make("list").with(&Txpr::make("real"));
        }
        if (type.factors[0]->name == "real") {
            return &Txpr::make("list").with(&Txpr::make("int"));
        }
    }

    return nullptr;
}

// 规则4：
// map<int, T> -> list<T>
Txpr* try_rule4(const Txpr& type) {
    if (type.name == "map") {
        if (type.factors[0]->name == "int") {
            return &Txpr::make("list").with(type.factors[1]->clone());
        }
    }

    return nullptr;
}

// 遍历所有收敛方式
void walk_reduce_way(const Txpr& type) {
    static auto casts = {
        //try_rule4,
        try_rule3,
        try_rule2,
        try_rule1,
    };

    std::queue<Txpr*> idles;
    idles.push(type.clone());

    while (!idles.empty()) {
        Txpr* cur = idles.front();
        idles.pop();

        // 穷举所有可能性（太暴力，根据类型这里并不需要全部）
        for (auto cast = casts.begin(); cast != casts.end(); cast++) {
            Txpr* result = (*cast)(*cur);
            if (result == nullptr) {
                continue;
            }

            std::cout << cur->string() << " -> " << result->string() << std::endl;
            idles.push(result);
        }

        // 遍历完毕之后要释放
        delete cur;
    }
}

#define SECTION(desc) \
    { std::cout << "-- " << (desc) << std::endl; }

int main() {
    SECTION("原子类型") {
        size_t pos = 0;
        std::unique_ptr<Txpr> type(Txpr::load("complex", pos));
        walk_reduce_way(*type);
    }

    SECTION("复杂点的list1") {
        size_t pos = 0;
        std::unique_ptr<Txpr> type(Txpr::load("list<int>", pos));
        walk_reduce_way(*type);
    }

    SECTION("复杂点的list2") {
        size_t pos = 0;
        std::unique_ptr<Txpr> type(Txpr::load("list<complex>", pos));
        walk_reduce_way(*type);
    }

    SECTION("复杂情况") {
        size_t pos = 0;
        std::unique_ptr<Txpr> type(
            Txpr::load("map<int, list<map<int, list<complex>>>>", pos));
        walk_reduce_way(*type);
    }

    SECTION("检测一个有二意性的场景(代码有点bug)") {
        size_t pos = 0;
        std::unique_ptr<Txpr> type(Txpr::load("map<int, map<int, int>>", pos));
        walk_reduce_way(*type);
    }

    return 0;
}
